﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Sol20 {

    public bool IsValid2(string s)//这样判断太麻烦了
    {
        //问题的关键是怎么遍历这个字符串
        Stack<char> stack = new Stack<char>();  

        for (int i = 0; i < s.Length; i++)
        {
            char kuohao = s[i];

            if (kuohao == '(')
            {
                stack.Push(kuohao);
            }
            if (kuohao == ')')
            {
                char top= stack.Pop();
                if (top != '(')
                {
                    return false;
                }
            }   if (kuohao == '[')
            {
                stack.Push(kuohao);
            }
            if (kuohao == ']')
            {
                if(stack.Count > 0)
                {
                    char top = stack.Pop();
                    if (top != '[')
                    {
                        return false;
                    }
                }
                else{
                    return false;
                }
               
                
            } if (kuohao == '{')
            {
                stack.Push(kuohao);
            }
            if (kuohao == '}')
            {
                char top= stack.Pop();
                if (top != '{')
                {
                    return false;
                }
            }


        }
        

        //入栈
        
        if(stack.Count > 0)
        {
            return false;
        }
       return true;

    }
    public bool IsValid(string s)//这样判断太麻烦了，使用字典存一个键值对
    {
        Stack<char> stack = new Stack<char>();  
        Dictionary<char, char> kuohaos = new Dictionary<char, char>(
            ){
            { '(', ')' }
        };
        kuohaos.Add( '[', ']' );
        kuohaos['{'] = '}';

        int len=s.Length;
        if (len%2!= 0)//判断一下奇偶，奇数直接返回false
        {
            return false;
        }

        for (int i=0; i<len;i++)
        {
            char c = s[i];
            if (kuohaos.ContainsKey(c))//是字典里面的key，也就是左括号
            {
stack.Push(c);
            }
            else//c是右括号
            {
                char left= stack.Pop();
                
                if(kuohaos[left] == c)//左右括号匹配
                {

                }
                else{
                    return false;
                }

            }

        }



        return (stack.Count==0);

    }


    }

class Program20
{

    static void Main20(string[] args)
    {
        string kuohao = "()[]{}";
        Sol20 sol = new Sol20();  
        bool isvalid = sol.IsValid(kuohao);
        Console.WriteLine(isvalid);
        Console.ReadKey();


    }
}


